package 剑指offer;

import 抽象数据类型.优先队列;

import java.util.*;

/**
 * @description:
 * @author: ywk
 * @date: 2021-04-09
 */
public class 出现次数的TopK问题 {
    //1.通过TreeMap
    public static String[][] topKstrings(String[] strings, int k) {
        // write code here
        TreeMap<String, Integer> map = new TreeMap(Comparator.naturalOrder());
        //维持数量为k
        for (int i = 0; i < strings.length; i++) {
            String str = strings[i];
            if (map.containsKey(str)) {
                map.put(str, map.get(str) + 1);
            } else {
                map.put(str, 1);
            }
        }
        ArrayList<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return -o1.getValue().compareTo(o2.getValue());
            }
        });
        String[][] result = new String[k][2];
        Iterator<Map.Entry<String, Integer>> iterator = list.iterator();
        int index = 0;
        while (index < k) {
            Map.Entry<String, Integer> next = iterator.next();
            result[index][0] = next.getKey();
            result[index][1] = next.getValue() + "";
            index++;
        }
        return result;
    }

    //2.自定义节点
    public static class Node implements Comparable<Node> {
        String key;
        Integer num;

        public Node(String key, Integer num) {
            this.key = key;
            this.num = num;
        }

        public String getKey() {
            return key;
        }

        public void setKey(String key) {
            this.key = key;
        }

        public Integer getNum() {
            return num;
        }

        public void setNum(Integer num) {
            this.num = num;
        }

        @Override
        public int compareTo(Node o) {
            if (this.num == o.num) {
                return -this.key.compareTo(o.key);
            }
            return this.num - o.num;
        }
    }

    public static String[][] topKStrings2(String[] strings, int k) {
        String[][] result = new String[k][2];
        Map<String, Integer> map = new HashMap<>();
        //维持数量为k
        for (int i = 0; i < strings.length; i++) {
            String str = strings[i];
            if (map.containsKey(str)) {
                map.put(str, map.get(str) + 1);
            } else {
                map.put(str, 1);
            }
        }
        Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
        TreeSet<Node> pq = new TreeSet<>((o1, o2) -> -o1.compareTo(o2));
        while (iterator.hasNext()) {
            Map.Entry<String, Integer> next = iterator.next();
            Node node = new Node(next.getKey(), next.getValue());
            if (pq.size() < k) {
                pq.add(node);
            } else {
                if (pq.last().compareTo(node) < 0) {
                    pq.pollLast();
                    pq.add(node);
                }
            }
        }
        Iterator<Node> iteratorSet = pq.iterator();
        int index = 0;
        while (index < k) {
            Node next = iteratorSet.next();
            result[index][0] = next.getKey();
            result[index][1] = next.getNum() + "";
            index++;
        }
        return result;
    }

    //3.通过自定义堆
    public static String[][] topKStrings3(String[] strings, int k) {
        String[][] result = new String[k][2];
        if(k==0){
            return   result;
        }
        Map<String, Integer> map = new HashMap<>();
        //维持数量为k
        for (int i = 0; i < strings.length; i++) {
            String str = strings[i];
            if (map.containsKey(str)) {
                map.put(str, map.get(str) + 1);
            } else {
                map.put(str, 1);
            }
        }
        优先队列.MaxPQ<Node> pq = new 优先队列.MaxPQ<>(k+1, false);
        Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, Integer> next = iterator.next();
            Node node = new Node(next.getKey(), next.getValue());
            if (pq.getN() < k) {
                pq.insert(node);
            } else {
                Node max = pq.max();
                if (max.compareTo(node) < 0) {
                    pq.delMax();
                    pq.insert(node);
                }
            }
        }
        int index = k - 1;
        while (index >= 0) {
            Node next = pq.delMax();
            result[index][0] = next.getKey();
            result[index][1] = next.getNum() + "";
            index--;
        }
        return result;
    }


    public static void main(String[] args) {
        topKStrings3(new String[]{"1",  "4", "4","2", "2"}, 2);
    }

}
